package org.pupil.search.binarySearch;

import org.pupil.search.ISearch;

import java.util.Arrays;

/**
 * @Description: 二分搜索：在有序数组中确定num存在还是不存在
 * @Author: pupil
 * @Date: 2024/08/01 下午 2:11
 */
public class FindNumber {

    public static void main(String[] args) {
        // 数据数组最大长度
        int N = 100;
        // 随机数组每个值，在1~V之间随机
        int V = 1000;
        // 测试次数
        int testNumber = 50000;
        System.out.println("测试开始");

        for (int i = 0; i < testNumber; i++) {
            int n = (int) (Math.random() * N);
            int[] arr = ISearch.randomArray(n, V);
            Arrays.sort(arr);
            int num = (int) (Math.random() * N);
            if (ISearch.right(arr, num) != exist(arr, num)) {
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 在有序数组中确定num存在还是不存在, 保证数组有序
     *
     * @param arr 数组
     * @param num 目标值
     * @return
     */
    public static boolean exist(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        //  左      右                中间值
        int l = 0, r = arr.length - 1, m = 0;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (arr[m] == num) {
                return true;
            } else if (arr[m] > num) { // 中间值大于目标值，往左缩小范围
                r = m - 1;
            } else { // 中间值小于目标值，往右缩小范围
                l = m + 1;
            }
        }
        return false;
    }





}
